The present invention relates to load balancing in parallel database systems.
Parallel database systems are known. Referring to FIG. 1, a block diagram is shown of a portion of an exemplary database system 100. The database system 100 shown is a parallel database system having multiple database nodes 101a-101n coupled to a communication medium 103 such as a bus, backplane, network segment, etc.
A database node 101n is illustrated in further detail. A database processor 111n is coupled via a bus 112n to an optional database co-processor 113n. Both the database processor 111n and the optional database co-processor 113n are coupled to memory 115n via buses 117n, 119n, and may be coupled to the same memory or to different memories. This parallel database configuration is merely exemplary of various configurations may be used to implement a database node of a parallel database system.
Parallel database systems allow for parallelization. FIG. 2 shows parallelization using traditional (explicit) shards, as is known in the art. With traditional shards, the database data and the associated management data (including indexes, strings, transaction state and schema catalog) are distributed across some number of address spaces (20), shown as in FIG. 2 as k address spaces. Within each address space is a subset of the database data (shown as data 0 through data k−1), as well as the associated indexes, strings, transaction states and schema catalog (22). Such parallelization may significantly improve search time.
In a parallel database system such as those of FIG. 1 and FIG. 2, data partitioning is often employed wherein tuples are partitioned according to a key value with different nodes being assigned tuples having key values within different assigned ranges or assigning tuples to nodes based on a hash of their key values. When the database is deployed using data partitioning, the number of tuples stored will ideally be balanced between the database nodes. In the course of database operation, the number of tuples stored may become unbalanced between database nodes. Such imbalance is referred to as data skew.
In parallel database systems data skew and execution skew are two well known obstacles to optimal performance of parallel database operations. Data skew occurs when tuples are unevenly distributed across the nodes of a database which can cause aggregate queries to perform only as good as the highest loaded node. Execution skew occurs when a query operation is imbalanced as it selects tuples from the nodes of a database. The present application addresses the problem of minimizing data skew on a parallel system where tuples are partitioned across the nodes according to a range partition scheme. The approach described herein is a system for monitoring and rebalancing data across the nodes so as to achieve an even distribution.
The context of the load balancing model described herein will be assumed to apply to shared-nothing parallel database architectures that partition data across nodes according to a range partitioning scheme. The goal of a load balancing architecture is to evenly distribute data across all the nodes of a database so that aggregate queries are executed with low response times. While the present application describes an approach for eliminating data skew, one could apply the same techniques to minimize execution skew.